package com.dbh.alg.algorithm.hot100.回溯;

/**
 *
 79. 单词搜索
 中等
 相关标签
 premium lock icon
 相关企业
 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。



 示例 1：


 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
 输出：true
 示例 2：


 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
 输出：true
 示例 3：


 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
 输出：false

 */
public class Leetcode79_单词搜索 {

    public boolean exist(char[][] board, String word) {
        // 获取网格的行和列
        int m = board.length;
        int n = board[0].length;

        // 创建访问标记数组，记录哪些单元格已经被访问过
        boolean[][] visited = new boolean[m][n];

        // 遍历网格中的每一个单元格，作为搜索的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从当前单元格开始深度优先搜索
                if (dfs(board, word, visited, i, j, 0)) {
                    // 如果找到匹配的路径，立即返回true
                    return  true;
                }
            }
        }
        return false;
    }

    /**
     * 深度优先搜索（回溯算法核心）
     * @param board 二维字符网格
     * @param word 要搜索的单词
     * @param visited 访问标记数组
     * @param i 当前行索引
     * @param j 当前列索引
     * @param index 当前要匹配的单词字符索引
     * @return 是否找到匹配的路径
     */
    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
        // 终止条件1：已经匹配完单词的所有字符
        if (index == word.length()) {
            return true;
        }

        // 终止条件2：当前单元格越界/已访问过/不匹配当前字符
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]
                || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 标记当前单元格为已访问
        visited[i][j] = true;

        // 向四个方向递归搜索（下、上、右、左）
        boolean found = dfs(board, word, visited, i + 1, j, index + 1)
        ||  dfs(board, word, visited, i - 1, j, index + 1) ||
                dfs(board, word, visited, i, j + 1, index + 1) ||
                dfs(board, word, visited, i, j - 1, index + 1);

        // 回溯：撤销当前单元格的访问标记（允许其他路径使用）
        visited[i][j] = false;

        // 返回是否找到有效路径
        return found;
    }
}
